/*
 * @Author: gitee_com_zb
 * @Date: 2024-12-10 14:59:59
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-12-10 15:00:22
 * @FilePath: /algorithm/每日一题10.最大连续1的个数III(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/max-consecutive-ones-iii
 */
class Solution {
public:
    // // 暴力枚举(超时) 时间复杂度O(N^2)
    // int longestOnes(vector<int>& nums, int k) {
    //     // 思路:找出最长的子数组,0的个数不超过k个
    //     int ret = 0;
    //     int n = nums.size();
    //     for (int i = 0; i < n; i++) {
    //         int zero = 0; // 记录0的个数
    //         for (int j = i; j < n; j++) {
    //             if (nums[j] == 0) zero++;
    //             if (zero <= k) ret = max(ret, j - i + 1);
    //             else break;
    //         }
    //     }
    //     return ret;
    // }

    // 滑动窗口 时间复杂度O(N)
    int longestOnes(vector<int>& nums, int k) {
        // 思路:找出最长的子数组,0的个数不超过k个
        int n = nums.size();
        int zero = 0, ret = 0; // 记录0的个数
        for (int left = 0, right = 0; right < n; right++) {
            if (nums[right] == 0)
                zero++;        // 进窗口
            while (zero > k) { // 判断
                if (nums[left] == 0)
                    zero--; // 出窗口
                left++;
            }
            ret = max(ret, right - left + 1); // 更新结果
        }
        return ret;
    }
};